package binaryTree;

public class Class112 {

    int sum=0;
    boolean res=false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null){
            return  false;
        }
        dfs(root,sum,targetSum);

        return res;
    }

    public void dfs(TreeNode root, int sum,int targetSum) {
        if (root == null) {
            return;
        }
        sum+=root.val;
        if (root.left == null && root.right == null) {
//            sb.delete(sb.length()-2, sb.length());
//            list.add(sb.toString());
//            sb.append("->");
            if (sum==targetSum){
                res=true;
            }
        }

        dfs(root.left, sum,targetSum);
        dfs(root.right, sum,targetSum);
        sum-=root.val; //回溯算法了
    }

    public static void main(String[] args) {
        Class112 class112 = new Class112();
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        treeNode1.left=treeNode2;
        boolean b = class112.hasPathSum(treeNode1, 0);
        System.out.println(b);

    }
}
